package DynamicProgramming;
/*
 * 回文子串
 */
public class lc647 {

        public int countSubstrings(String s) {
            char[] S = s.toCharArray();
            int len = S.length;
            boolean[][] dp = new boolean[len][len];
            int res = 0;
            for (int i = len - 1; i >= 0; i--) {
                for (int j = i; j < len; j++) {
                    if (S[i] == S[j]) {
                        if (j - i <= 1) {
                            dp[i][j] = true;
                            res++;
                        } else if (j - i > 1) {
                            if (dp[i + 1][j - 1]) {
                                dp[i][j] = true;
                                res++;
                            }
                        }
                    }
                }
            }
            return res;
        }

}
